/* This file is modified from SmallObj.cpp of loki-lib project.
 *
 * The original copyright:
 *
 * The Loki Library
 * Copyright (c) 2001 by Andrei Alexandrescu
 * This code accompanies the book:
 * Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design 
 *     Patterns Applied". Copyright (c) 2001. Addison-Wesley.
 * Permission to use, copy, modify, distribute and sell this software for any 
 *     purpose is hereby granted without fee, provided that the above  copyright 
 *     notice appear in all copies and that both that copyright notice and this 
 *     permission notice appear in supporting documentation.
 * The author or Addison-Wesley Longman make no representations about the 
 *     suitability of this software for any purpose. It is provided "as is" 
 *     without express or implied warranty.
 */

#include <stdio.h>
#include <stdint.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#include "imbus_internal.h"
#include "im_memory.h"

#define IM_MEMORY_DEFAULT_PAGE_SIZE         4096
#define IM_MEMORY_MAX_BLOCK_SIZE            256

#ifdef SIZEOF_SIZE_T
#define IM_MEMORY_DEFAULT_ALIGNMENT         SIZEOF_SIZE_T
#else
#define IM_MEMORY_DEFAULT_ALIGNMENT         4
#endif

#define IM_MEMORY_GET_FIXED_OFFSET(size)    (((size) + IM_MEMORY_DEFAULT_ALIGNMENT - 1)/IM_MEMORY_DEFAULT_ALIGNMENT)
#define IM_MEMORY_NUM_OF_FIXED              IM_MEMORY_GET_FIXED_OFFSET(IM_MEMORY_MAX_BLOCK_SIZE)

#define IM_MEMORY_DO_EXTRA_TEST

/*************************** Declaration ************************/
typedef struct _Chunk       Chunk;
typedef struct _Fixed       Fixed;

/** @struct Chunk
 Contains info about each allocated Chunk - which is a collection of
 contiguous blocks.  Each block is the same size, as specified by the
 Fixed.  The number of blocks in a Chunk depends upon page size.
 This is a POD-style struct with value-semantics.  All functions and data
 are private so that they can not be changed by anything other than the
 Fixed which owns the Chunk.

 @par Minimal Interface
 For the sake of runtime efficiency, no constructor, destructor, or
 copy-assignment operator is defined. The inline functions made by the
 compiler should be sufficient, and perhaps faster than hand-crafted
 functions.  The lack of these functions allows vector to create and copy
 Chunks as needed without overhead.  The Init and Release functions do
 what the default constructor and destructor would do.  A Chunk is not in
 a usable state after it is constructed and before calling Init.  Nor is
 a Chunk usable after Release is called, but before the destructor.

 @par Efficiency
 Down near the lowest level of the allocator, runtime efficiencies trump
 almost all other considerations.  Each function does the minimum required
 of it.  All functions should execute in constant time to prevent higher-
 level code from unwittingly using a version of Shlemiel the Painter's
 Algorithm.

 @par Stealth Indexes
 The first char of each empty block contains the index of the next empty
 block.  These stealth indexes form a singly-linked list within the blocks.
 A Chunk is corrupt if this singly-linked list has a loop or is shorter
 than blocksAvailable_.  Much of the allocator's time and space efficiency
 comes from how these stealth indexes are implemented.
 */
struct _Chunk
{
    /* Pointer to array of allocated blocks. */
    IMUChar *data;
    /* Index of first empty block. */
    IMUChar  first_available_block;
    /* Count of empty blocks. */
    IMUChar  blocks_available;
};

/** @struct Fixed
 Offers services for allocating fixed-sized objects.  It has a container
 of "containers" of fixed-size blocks.  The outer container has all the
 Chunks.  The inner container is a Chunk which owns some blocks.

 @par Class Level Invariants
 - There is always either zero or one Chunk which is empty.
 - If this has no empty Chunk, then emptyChunk_ is NULL.
 - If this has an empty Chunk, then emptyChunk_ points to it.
 - If the Chunk container is empty, then deallocChunk_ and allocChunk_
   are NULL.
 - If the Chunk container is not-empty, then deallocChunk_ and allocChunk_
   are either NULL or point to Chunks within the container.
 - allocChunk_ will often point to the last Chunk in the container since
   it was likely allocated most recently, and therefore likely to have an
   available block.
 */
struct _Fixed
{
    /* Number of bytes in a single block within a Chunk. */
    IMSize   block_size;
    /* Number of blocks managed by each Chunk. */
    IMUChar  num_blocks;

    /* Container of Chunks */
    Chunk   *start;
    Chunk   *finish;
    Chunk   *end_of_storage;

    /* Pointer to Chunk used for last or next allocation. */
    Chunk   *alloc_chunk;
    /* Pointer to Chunk used for last or next deallocation. */
    Chunk   *dealloc_chunk;
    /* Pointer to the only empty Chunk if there is one, else NULL. */
    Chunk   *empty_chunk;

#if IM_ENABLE_DEBUG
    IMInt    alloc_count;
#endif
};

/* Fixed pool */
static Fixed            __fixed_pool [IM_MEMORY_NUM_OF_FIXED];
static IMBool           __fixed_pool_initted = FALSE;

/******************* Declaration of internal functions *******************/
static inline IMBool    chunk_init                  (Chunk      *chunk,
                                                     IMSize      block_size,
                                                     IMUChar     blocks);
static inline IMPointer chunk_allocate              (Chunk      *chunk,
                                                     IMSize      block_size);
static inline void      chunk_deallocate            (Chunk      *chunk,
                                                     IMSize      block_size,
                                                     IMPointer   p);
static inline void      chunk_reset                 (Chunk      *chunk,
                                                     IMSize      block_size,
                                                     IMUChar     blocks);
static inline void      chunk_release               (Chunk      *chunk);
static inline IMBool    chunk_is_corrupt            (Chunk      *chunk,
                                                     IMSize      block_size,
                                                     IMUChar     blocks,
                                                     IMBool      check_indexes);
static inline IMBool    chunk_is_block_available    (Chunk      *chunk,
                                                     IMSize      block_size,
                                                     IMUChar     blocks,
                                                     IMPointer   p);
static inline IMBool    chunk_has_block             (Chunk      *chunk,
                                                     IMSize      chunk_length,
                                                     IMPointer   p);
static inline IMBool    chunk_has_available         (Chunk      *chunk,
                                                     IMUChar     blocks);
static inline IMBool    chunk_is_filled             (Chunk      *chunk);

static inline void      fixed_init                  (Fixed      *fixed,
                                                     IMSize      block_size,
                                                     IMSize      page_size);
static inline void      fixed_release               (Fixed      *fixed);
static inline IMPointer fixed_allocate              (Fixed      *fixed);
static inline IMBool    fixed_deallocate            (Fixed      *fixed,
                                                     IMPointer   p,
                                                     Chunk      *hint);
static inline IMBool    fixed_trim_empty_chunk      (Fixed      *fixed);
static inline IMBool    fixed_trim_chunk_list       (Fixed      *fixed);
static inline IMSize    fixed_count_empty_chunks    (Fixed      *fixed);
static inline IMBool    fixed_is_corrupt            (Fixed      *fixed);
static inline Chunk*    fixed_has_block             (Fixed      *fixed,
                                                     IMPointer   p);
static inline IMBool    fixed_make_new_chunk        (Fixed      *fixed);
static inline Chunk*    fixed_vicinity_find         (Fixed      *fixed,
                                                     IMPointer   p);
static inline IMSize    fixed_get_block_size        (Fixed      *fixed);

static inline IMBool    im_slice_trim_excess_memory();

/****************** Implementation of public functions ********************/
void
im_slice_init ()
{
    if (!__fixed_pool_initted) {
        IMSize i;
        for (i = 0; i < IM_MEMORY_NUM_OF_FIXED; ++i) 
            fixed_init (& __fixed_pool [i], (i + 1) * IM_MEMORY_DEFAULT_ALIGNMENT, IM_MEMORY_DEFAULT_PAGE_SIZE);

        __fixed_pool_initted = TRUE;
    }
}

IMPointer
im_slice_alloc (IMSize block_size)
{
    IMSize       idx;
    Fixed       *fixed;
    IMPointer    p;

    if (block_size > IM_MEMORY_MAX_BLOCK_SIZE)
        return im_malloc (block_size);

    if (!__fixed_pool_initted) im_slice_init ();

    if (!block_size) block_size = 1;

    idx = IM_MEMORY_GET_FIXED_OFFSET(block_size) - 1;

    _im_assert (idx < IM_MEMORY_NUM_OF_FIXED);

    fixed = & __fixed_pool [idx];

    _im_assert (fixed_get_block_size (fixed) >= block_size);
    _im_assert (fixed_get_block_size (fixed) < block_size + IM_MEMORY_DEFAULT_ALIGNMENT);

    p = fixed_allocate (fixed);

    if (!p && im_slice_trim_excess_memory ())
        p = fixed_allocate (fixed);

    _im_assert (p);

    return p;
}

IMPointer
im_slice_alloc0 (IMSize block_size)
{
    IMPointer p = im_slice_alloc (block_size);

    if (p)
        memset (p, 0, block_size);

    return p;
}

void
im_slice_free (IMSize block_size, IMPointer block)
{
    IMSize  idx;
    Fixed  *fixed;
    IMBool  found;

    if (!block) return;

    if (block_size > IM_MEMORY_MAX_BLOCK_SIZE) {
        im_free (block);
        return;
    }

    _im_assert (__fixed_pool_initted && "im_slice_init () should be called first.");

    if (!block_size) block_size = 1;

    idx = IM_MEMORY_GET_FIXED_OFFSET(block_size) - 1;

    _im_assert (idx < IM_MEMORY_NUM_OF_FIXED);

    fixed = & __fixed_pool [idx];

    _im_assert (fixed_get_block_size (fixed) >= block_size);
    _im_assert (fixed_get_block_size (fixed) < block_size + IM_MEMORY_DEFAULT_ALIGNMENT);

    found = fixed_deallocate (fixed, block, 0);

    _im_assert (found);
}

IMPointer
im_malloc (IMSize n_bytes)
{
    IMPointer p = malloc (n_bytes);

    _im_assert (p);

    return p;
}

IMPointer
im_malloc0 (IMSize n_bytes)
{
    IMPointer p = malloc (n_bytes);

    _im_assert (p);

    memset (p, 0, n_bytes);

    return p;
}

IMPointer
im_realloc (IMPointer mem, IMSize n_bytes)
{
    IMPointer p = realloc (mem, n_bytes);

    _im_assert (p);

    return p;
}

void
im_free (IMPointer mem)
{
    free (mem);
}

/********************** Implementation of Chunk ************************/
/** Initializes a just-constructed Chunk.
 @param blockSize Number of bytes per block.
 @param blocks Number of blocks per Chunk.
 @return True for success, false for failure.
 */
static inline IMBool
chunk_init (Chunk *chunk, IMSize block_size, IMUChar blocks)
{
    IMSize alloc_size;

    _im_assert (chunk);
    _im_assert (block_size > 0);
    _im_assert (blocks > 0);

    alloc_size = block_size *blocks;

    _im_assert (alloc_size / block_size == blocks);

    chunk->data = (IMUChar *) im_malloc (alloc_size);

    _im_assert (chunk->data);

    if (!chunk->data)
        return FALSE;

    chunk_reset (chunk, block_size, blocks);

    return TRUE;
}

/** Resets the Chunk back to pristine values. The available count is
 set back to zero, and the first available index is set to the zeroth
 block.  The stealth indexes inside each block are set to point to the
 next block. This assumes the Chunk's data was already using Init.
 */
static inline void
chunk_reset (Chunk *chunk, IMSize block_size, IMUChar blocks)
{
    IMUChar i = 0;
    IMUChar *p = 0;

    _im_assert (chunk);
    _im_assert (block_size > 0);
    _im_assert (blocks > 0);
    _im_assert ((block_size * blocks) / block_size == blocks);

    chunk->first_available_block = 0;
    chunk->blocks_available = blocks;

    for (p = chunk->data; i != blocks; p += block_size)
        *p = ++i;
}

/* Releases the allocated block of memory.
 */
static inline void
chunk_release (Chunk *chunk)
{
    _im_assert (chunk);

    im_free (chunk->data);
}

/** Allocate a block within the Chunk.  Complexity is always O(1), and
 this will never throw.  Does not actually "allocate" by calling
 malloc, new, or any other function, but merely adjusts some internal
 indexes to indicate an already allocated block is no longer available.
 @return Pointer to block within Chunk.
 */
static inline IMPointer
chunk_allocate (Chunk *chunk, IMSize block_size)
{
    IMUChar fab;
    IMUChar *result;

    _im_assert (chunk);

    if (chunk_is_filled (chunk))
        return 0;

    fab = chunk->first_available_block;

    _im_assert ((fab * block_size) / block_size == fab);

    result = chunk->data + (fab * block_size);

    chunk->first_available_block = *result;

    --chunk->blocks_available;

    return result;
}

/** Deallocate a block within the Chunk. Complexity is always O(1), and
 this will never throw.  For efficiency, this assumes the address is
 within the block and aligned along the correct byte boundary.  An
 _im_assertion checks the alignment, and a call to HasBlock is done from
 within VicinityFind.  Does not actually "deallocate" by calling free,
 delete, or other function, but merely adjusts some internal indexes to
 indicate a block is now available.
 */
static inline void
chunk_deallocate (Chunk *chunk, IMSize block_size, IMPointer p)
{
    IMUChar *r = (IMUChar *) p;
    IMUChar idx;

    _im_assert (chunk);
    _im_assert (r >= chunk->data);

    _im_assert ((r - chunk->data) % block_size == 0);

    idx = (IMUChar) ((r - chunk->data) / block_size);

    if (chunk->blocks_available > 0)
        _im_assert (chunk->first_available_block != idx);

    *r = chunk->first_available_block;

    chunk->first_available_block = idx;

    _im_assert (chunk->first_available_block == (r - chunk->data) / block_size);

    ++ chunk->blocks_available;
}

/** Determines if the Chunk has been corrupted.
 @param numBlocks Total # of blocks in the Chunk.
 @param blockSize # of bytes in each block.
 @param checkIndexes True if caller wants to check indexes of available
  blocks for corruption.  If false, then caller wants to skip some
  tests tests just to run faster.  (Debug version does more checks, but
  release version runs faster.)
 @return True if Chunk is corrupt.
 */
static inline IMBool
chunk_is_corrupt (Chunk *chunk, IMSize block_size, IMUChar blocks, IMBool check_indexes)
{
    IMUChar idx;
    IMUChar found [UCHAR_MAX];
    IMUChar *next = 0;
    IMUChar cc = 0;


    _im_assert (chunk);

    if (chunk->blocks_available > blocks) {
        /* The chunk has been corrupted. */
        _im_assert (FALSE);
        return TRUE;
    }

    if (chunk_is_filled (chunk))
        return FALSE;

    idx = chunk->first_available_block;

    if (idx >= blocks) {
        /* The chunk has been corrupted */ 
        _im_assert (FALSE);
        return TRUE;
    }

    if (!check_indexes)
        return FALSE;

    /* Check index */
    memset (found, 0, UCHAR_MAX);

    for (cc = 0;;) {
        found [idx] = 1;
        next = chunk->data + (idx * block_size);

        ++cc;
        if (cc >= chunk->blocks_available)
            break;

        idx = *next;
        if (idx >= blocks) {
            /* An index beyond chunk boundary has been found. */
            _im_assert (FALSE);
            return TRUE;
        }
        if (found [idx]) {
            /* A loop in linked-list has been found. */
            _im_assert (FALSE);
            return TRUE;
        }
    }

    return FALSE;
}

/** Determines if block is available.
 @param blockSize # of bytes in each block.
 @param numBlocks Total # of blocks in the Chunk.
 @param p Address of block managed by Chunk.
 @return True if block is available, else false if allocated.
 */
static inline IMBool
chunk_is_block_available (Chunk *chunk, IMSize block_size, IMUChar blocks, IMPointer p)
{
    IMUChar *bp;
    IMUChar *next;
    IMUChar blk_idx;
    IMUChar idx;
    IMUChar found [UCHAR_MAX];
    IMUChar cc = 0;

    _im_assert (chunk);

    if (chunk_is_filled (chunk))
        return FALSE;

    bp = (IMUChar *) p;

    /* Alignment check */
    _im_assert ( (bp - chunk->data) % block_size == 0);

    blk_idx = (IMUChar) ((bp - chunk->data) / block_size);
    idx = chunk->first_available_block;

    _im_assert (blocks > idx);

    if (idx == blk_idx)
        return TRUE;

    memset (found, 0, UCHAR_MAX);

    for (cc = 0;;) {
        found [idx] = 1;
        next = chunk->data + (idx * block_size);

        ++cc;
        if (cc >= chunk->blocks_available)
            break;

        idx = *next;
        if (idx == blk_idx)
            return TRUE;
        _im_assert (blocks > idx);
        _im_assert (!found [idx]);
    }

    return FALSE;
}

/* Returns true if block at address P is inside this Chunk.
 */
static inline IMBool
chunk_has_block (Chunk *chunk, IMSize chunk_length, IMPointer p)
{
    _im_assert (chunk);

    return (((IMUChar *)p) >= chunk->data && ((IMUChar *)p) < (chunk->data + chunk_length));
}

static inline IMBool
chunk_has_available (Chunk *chunk, IMUChar blocks)
{
    _im_assert (chunk);

    return (chunk->blocks_available == blocks);
}

static inline IMBool
chunk_is_filled (Chunk *chunk)
{
    _im_assert (chunk);

    return chunk->blocks_available == 0;
}

/********************** Implementation of Fixed ************************/
/* Initializes a Fixed by calculating # of blocks per Chunk.
 */
static inline void
fixed_init (Fixed *fixed, IMSize block_size, IMSize page_size)
{
    IMSize num_blocks;

    _im_assert (fixed);
    _im_assert (block_size > 0);
    _im_assert (page_size >= block_size);

    fixed->block_size      = block_size;
    fixed->start           = 0;
    fixed->finish          = 0;
    fixed->end_of_storage  = 0;
    fixed->alloc_chunk     = 0;
    fixed->dealloc_chunk   = 0;
    fixed->empty_chunk     = 0;

#if IM_ENABLE_DEBUG
    fixed->alloc_count     = 0;
#endif

    num_blocks              = page_size / block_size;

    if (num_blocks > UCHAR_MAX)
        num_blocks = UCHAR_MAX;
    else if (num_blocks < 8)
        num_blocks = 8;

    fixed->num_blocks = (IMUChar) num_blocks;
}

static inline void
fixed_release (Fixed *fixed)
{
    Chunk *i;

#ifdef IM_MEMORY_DO_EXTRA_TEXT
    fixed_trim_empty_chunk (fixed);
    _im_assert (fixed->start == fixed->finish);
#endif

    for (i = fixed->start; i != fixed->finish; ++i)
        chunk_release (i);
}

/** Returns pointer to allocated memory block of fixed size - or NULL
  if it failed to allocate.
 */
static inline IMPointer
fixed_allocate (Fixed *fixed)
{
    IMPointer p;

    _im_assert (fixed);
    _im_assert (!fixed->empty_chunk || chunk_has_available (fixed->empty_chunk, fixed->num_blocks));
    _im_assert (fixed_count_empty_chunks (fixed) < 2);

    if (!fixed->alloc_chunk || chunk_is_filled (fixed->alloc_chunk)) {
        if (fixed->empty_chunk) {
            fixed->alloc_chunk = fixed->empty_chunk;
            fixed->empty_chunk = 0;
        } else {
            Chunk *i;
            for (i=fixed->start; i != fixed->finish; ++i) {
                if (!chunk_is_filled (i)) {
                    fixed->alloc_chunk = i;
                    break;
                }
            }
            if (i == fixed->finish && !fixed_make_new_chunk (fixed))
                return 0;
        }
    } else if (fixed->alloc_chunk == fixed->empty_chunk) {
        fixed->empty_chunk = 0;
    }

    _im_assert (fixed->alloc_chunk);
    _im_assert (!chunk_is_filled (fixed->alloc_chunk));

    p = chunk_allocate (fixed->alloc_chunk, fixed->block_size);

    _im_assert (!fixed->empty_chunk || chunk_has_available (fixed->empty_chunk, fixed->num_blocks));
    _im_assert (fixed_count_empty_chunks (fixed) < 2);

#if IM_ENABLE_DEBUG
    ++ fixed->alloc_count;
#endif

    return p;
}

/** Deallocate a memory block previously allocated with Allocate.  If
 the block is not owned by this Fixed, it returns false so
 that SmallObjAllocator can call the default deallocator.  If the
 block was found, this returns true.
 */
static inline IMBool
fixed_deallocate (Fixed *fixed, IMPointer p, Chunk *hint)
{
    Chunk *found_chunk;

    _im_assert (fixed);
    _im_assert (fixed->start);
    _im_assert (fixed->finish > fixed->start);
    _im_assert (fixed->end_of_storage >= fixed->finish);
    _im_assert (fixed->start <= fixed->dealloc_chunk && fixed->finish > fixed->dealloc_chunk);
    _im_assert (fixed->start <= fixed->alloc_chunk && fixed->finish > fixed->alloc_chunk);
    _im_assert (fixed_count_empty_chunks (fixed) < 2);

    found_chunk = (hint ? hint : fixed_vicinity_find (fixed, p));

    if (!found_chunk)
        return FALSE;

    _im_assert (chunk_has_block (found_chunk, fixed->num_blocks * fixed->block_size, p));

#ifdef IM_MEMORY_DO_EXTRA_TEST
    if (chunk_is_corrupt (found_chunk, fixed->block_size, fixed->num_blocks, TRUE)) {
        _im_assert (FALSE);
        return FALSE;
    }
    if (chunk_is_block_available (found_chunk, fixed->block_size, fixed->num_blocks, p)) {
        _im_assert (FALSE);
        return FALSE;
    }
#endif
    fixed->dealloc_chunk = found_chunk;

    /* Do deallocate */
    _im_assert (fixed->empty_chunk != fixed->dealloc_chunk);
    _im_assert (!chunk_has_available (fixed->dealloc_chunk, fixed->num_blocks));
    _im_assert (!fixed->empty_chunk || chunk_has_available (fixed->empty_chunk, fixed->num_blocks));

    chunk_deallocate (fixed->dealloc_chunk, fixed->block_size, p);

    if (chunk_has_available (fixed->dealloc_chunk, fixed->num_blocks)) {
        /* deallocChunk_ is empty, but a Chunk is only released if there are 2
         * empty chunks.  Since emptyChunk_ may only point to a previously
         * cleared Chunk, if it points to something else besides deallocChunk_,
         * then Fixed currently has 2 empty Chunks.
         */
        if (fixed->empty_chunk) {
            /* If last Chunk is empty, just change what deallocChunk_
             * points to, and release the last.  Otherwise, swap an empty
             * Chunk with the last, and then release it.
             */
            Chunk *last_chunk = fixed->finish - 1;
            if (last_chunk == fixed->dealloc_chunk)
                fixed->dealloc_chunk = fixed->empty_chunk;
            else if (last_chunk != fixed->empty_chunk)
                IM_SWAP(Chunk, *fixed->empty_chunk, *last_chunk);

            _im_assert (chunk_has_available (last_chunk, fixed->num_blocks));

            chunk_release (last_chunk);
            --fixed->finish;

            if (fixed->alloc_chunk == last_chunk || chunk_is_filled (fixed->alloc_chunk))
                fixed->alloc_chunk = fixed->dealloc_chunk;
        }
        fixed->empty_chunk = fixed->dealloc_chunk;
    }

    /* prove either _empty_chunk points nowhere, or points to a truly empty Chunk. */
    _im_assert (!fixed->empty_chunk || chunk_has_available (fixed->empty_chunk, fixed->num_blocks));

    _im_assert (fixed_count_empty_chunks (fixed) < 2);

#if IM_ENABLE_DEBUG
    -- fixed->alloc_count;
#endif

    return TRUE;
}

/** Releases the memory used by the empty Chunk.  This will take
 constant time under any situation.
 @return True if empty chunk found and released, false if none empty.
 */
static inline IMBool
fixed_trim_empty_chunk (Fixed *fixed)
{
    Chunk *last_chunk;

    _im_assert (fixed);

    if (!fixed->empty_chunk)
        return FALSE;

    /* the chunk list is not empty */
    _im_assert (fixed->start);
    _im_assert (fixed->finish > fixed->start);
    _im_assert (fixed->end_of_storage >= fixed->finish);
    /* prove _empty_chunk points to a truly empty Chunk. */
    _im_assert (chunk_has_available (fixed->empty_chunk, fixed->num_blocks));
    /* There should be exactly 1 empty Chunk. */
    _im_assert (fixed_count_empty_chunks (fixed) == 1);

    last_chunk = fixed->finish - 1;

    if (last_chunk != fixed->empty_chunk)
        IM_SWAP(Chunk, *fixed->empty_chunk, *last_chunk);

    _im_assert (chunk_has_available (last_chunk, fixed->num_blocks));

    chunk_release (last_chunk);
    --fixed->finish;

    if (fixed->start == fixed->finish) {
        fixed->alloc_chunk = 0;
        fixed->dealloc_chunk = 0;
    } else {
        if (fixed->dealloc_chunk == fixed->empty_chunk)
            fixed->dealloc_chunk = fixed->start;

        if (fixed->alloc_chunk == fixed->empty_chunk)
            fixed->alloc_chunk = fixed->start;
    }

    fixed->empty_chunk = 0;

    _im_assert (fixed_count_empty_chunks (fixed) == 0);

    return TRUE;
}

/** Releases unused spots from ChunkList.  This takes constant time
 with respect to # of Chunks, but actual time depends on underlying
 memory allocator.
 @return False if no unused spots, true if some found and released.
 */
static inline IMBool
fixed_trim_chunk_list (Fixed *fixed)
{
    IMSize num;
    IMSize empty_off;
    IMSize alloc_off;
    IMSize dealloc_off;

    _im_assert (fixed);

    if (!fixed->start || fixed->start == fixed->finish) {
        _im_assert (!fixed->alloc_chunk);
        _im_assert (!fixed->dealloc_chunk);
        return FALSE;
    }

    if (fixed->finish == fixed->end_of_storage)
        return FALSE;

    num = fixed->finish - fixed->start;

    if (fixed->empty_chunk)
        empty_off = fixed->empty_chunk - fixed->start;
    else
        empty_off = num;

    if (fixed->alloc_chunk)
        alloc_off = fixed->alloc_chunk - fixed->start;
    else
        alloc_off = num;

    if (fixed->dealloc_chunk)
        dealloc_off = fixed->dealloc_chunk - fixed->start;
    else
        dealloc_off = num;

    fixed->start = (Chunk *) im_realloc (fixed->start, num * sizeof (Chunk));

    fixed->finish = fixed->start + num;
    fixed->end_of_storage = fixed->finish;

    if (alloc_off < num)
        fixed->alloc_chunk = fixed->start + alloc_off;
    if (dealloc_off < num)
        fixed->dealloc_chunk = fixed->start + dealloc_off;
    if (empty_off < num)
        fixed->empty_chunk = fixed->start + empty_off;

    return TRUE;
}

/** Returns count of empty Chunks held by this allocator.  Complexity
 is O(C) where C is the total number of Chunks - empty or used.
 */
static inline IMSize
fixed_count_empty_chunks (Fixed *fixed)
{
#ifdef IM_MEMORY_DO_EXTRA_TEST
    IMSize count = 0;
    Chunk *i;
    for (i = fixed->start; i != fixed->finish; ++i) {
        if (chunk_has_available (i, fixed->num_blocks))
            ++count;
    }
    return count;
#else
    return (fixed->empty_chunk ? 1 : 0);
#endif
}

/** Determines if Fixed is corrupt.  Checks data members to
 see if any have erroneous values, or violate class invariants.  It
 also checks if any Chunk is corrupt.  Complexity is O(C) where C is
 the number of Chunks.  If any data is corrupt, this will return true
 in release mode, or _im_assert in debug mode.
 */
static inline IMBool
fixed_is_corrupt (Fixed *fixed)
{
    IMSize empty_count;
    Chunk  *i;

    _im_assert (fixed);

    empty_count = fixed_count_empty_chunks (fixed);

    /* Empty */
    if (!fixed->start || fixed->start == fixed->finish) {
        if (fixed->start != fixed->finish) {
            _im_assert (FALSE);
            return TRUE;
        }
        if (fixed->end_of_storage < fixed->finish) {
            _im_assert (FALSE);
            return TRUE;
        }
        if (empty_count) {
            _im_assert (FALSE);
            return TRUE;
        }
        if (fixed->dealloc_chunk) {
            _im_assert (FALSE);
            return TRUE;
        }
        if (fixed->alloc_chunk) {
            _im_assert (FALSE);
            return TRUE;
        }
        if (fixed->empty_chunk) {
            _im_assert (FALSE);
            return TRUE;
        }
    } else {
        if (fixed->start > fixed->finish) {
            _im_assert (FALSE);
            return TRUE;
        }
        if (fixed->finish > fixed->end_of_storage) {
            _im_assert (FALSE);
            return TRUE;
        }
        if (fixed->dealloc_chunk >= fixed->finish) {
            _im_assert (FALSE);
            return TRUE;
        }
        if (fixed->dealloc_chunk < fixed->start) {
            _im_assert (FALSE);
            return TRUE;
        }
        if (fixed->alloc_chunk >= fixed->finish) {
            _im_assert (FALSE);
            return TRUE;
        }
        if (fixed->alloc_chunk < fixed->start) {
            _im_assert (FALSE);
            return TRUE;
        }

        switch (empty_count) {
            case 0:
                if (fixed->empty_chunk) {
                    _im_assert (FALSE);
                    return TRUE;
                }
                break;
            case 1:
                if (!fixed->empty_chunk) {
                    _im_assert (FALSE);
                    return TRUE;
                }
                if (fixed->empty_chunk >= fixed->finish) {
                    _im_assert (FALSE);
                    return TRUE;
                }
                if (fixed->empty_chunk < fixed->start) {
                    _im_assert (FALSE);
                    return TRUE;
                }
                if (!chunk_has_available (fixed->empty_chunk, fixed->num_blocks)) {
                    _im_assert (FALSE);
                    return TRUE;
                }
                break;
            default:
                _im_assert (FALSE);
                return TRUE;
        }
        for (i = fixed->start; i != fixed->finish; ++i) {
            if (chunk_is_corrupt (i, fixed->block_size, fixed->num_blocks, TRUE))
                return TRUE;
        }
    }

    return FALSE;
}

/** Returns true if the block at address p is within a Chunk owned by
 this Fixed.  Complexity is O(C) where C is the total number
 of Chunks - empty or used.
 */
static inline Chunk*
fixed_has_block (Fixed *fixed, IMPointer p)
{
    IMSize chunk_length;
    Chunk  *i;
   
    _im_assert (fixed);

    chunk_length = fixed->num_blocks * fixed->block_size;

    for (i = fixed->start; i != fixed->finish; ++i) {
        if (chunk_has_block (i, chunk_length, p))
            return i;
    }

    return 0;
}

/** Creates an empty Chunk and adds it to the end of the ChunkList.
 All calls to the lower-level memory allocation functions occur inside
 this function, and so the only try-catch block is inside here.
 @return true for success, false for failure.
 */
static inline IMBool
fixed_make_new_chunk (Fixed *fixed)
{
    IMSize size;
    IMSize new_size;

    _im_assert (fixed);
    _im_assert (!fixed->empty_chunk);

    size = fixed->finish - fixed->start;

    if (fixed->finish == fixed->end_of_storage) {
        new_size = (size ? (size * 2) : 8);

        fixed->start = (Chunk *) im_realloc (fixed->start, new_size * sizeof (Chunk));

        _im_assert (fixed->start);

        fixed->finish = fixed->start + size;
        fixed->end_of_storage = fixed->start + new_size;
    }

    if (!chunk_init (fixed->finish, fixed->block_size, fixed->num_blocks))
        return FALSE;

    fixed->alloc_chunk = fixed->finish;
    fixed->dealloc_chunk = fixed->start;

    ++fixed->finish;

    return TRUE;
}

/** Finds the Chunk which owns the block at address p.  It starts at
 deallocChunk_ and searches in both forwards and backwards directions
 from there until it finds the Chunk which owns p.  This algorithm
 should find the Chunk quickly if it is deallocChunk_ or is close to it
 in the Chunks container.  This goes both forwards and backwards since
 that works well for both same-order and opposite-order deallocations.
 (Same-order = objects are deallocated in the same order in which they
 were allocated.  Opposite order = objects are deallocated in a last to
 first order.  Complexity is O(C) where C is count of all Chunks.  This
 never throws.
 @return Pointer to Chunk that owns p, or NULL if no owner found.
 */
static inline Chunk*
fixed_vicinity_find (Fixed *fixed, IMPointer p)
{
    IMSize chunk_length;
    Chunk *lo;
    Chunk *hi;

    _im_assert (fixed);

    if (!fixed->start || fixed->finish == fixed->start)
        return 0;

    _im_assert (fixed->dealloc_chunk);

    chunk_length = fixed->num_blocks * fixed->block_size;
    lo = fixed->dealloc_chunk;
    hi = fixed->dealloc_chunk + 1;

    /* Special case: _dealloc_chunk is the last in the array */
    if (hi == fixed->finish) hi = 0;

    for (;;) {
        if (lo) {
            if (chunk_has_block (lo, chunk_length, p))
                return lo;

            if (lo-- == fixed->start) {
                lo = 0;
                if (!hi) break;
            }
        }

        if (hi) {
            if (chunk_has_block (hi, chunk_length, p))
                return hi;

            if (++hi == fixed->finish) {
                hi = 0;
                if (!lo) break;
            }
        }
    }

    return 0;
}

static inline IMSize
fixed_get_block_size (Fixed *fixed)
{
    _im_assert (fixed);

    return fixed->block_size;
}

static inline IMBool
im_slice_trim_excess_memory()
{
    IMBool found = FALSE;
    IMSize i;

    for (i = 0; i < IM_MEMORY_NUM_OF_FIXED; ++i)
        if (fixed_trim_empty_chunk (& __fixed_pool [i]))
            found = TRUE;

    for (i = 0; i < IM_MEMORY_NUM_OF_FIXED; ++i)
        if (fixed_trim_chunk_list (& __fixed_pool [i]))
            found = TRUE;

    return found;
}

#if IM_ENABLE_DEBUG
IMBool
_im_slice_is_corrupt()
{
    IMSize i;

    if (!__fixed_pool_initted) im_slice_init ();

    for (i = 0; i < IM_MEMORY_NUM_OF_FIXED; ++i)
        if (fixed_is_corrupt (& __fixed_pool [i]))
            return TRUE;

    return FALSE;
}

void
_im_slice_print_debug_info()
{
    fprintf (stderr, "Slice system debuginfo:\n");
    if (__fixed_pool_initted) {
        IMSize i;
        for (i = 0; i < IM_MEMORY_NUM_OF_FIXED; ++i) {
            if (__fixed_pool [i].alloc_count)
                fprintf (stderr, "%3lu : allocated %d blocks.\n",
                     __fixed_pool [i].block_size, 
                     __fixed_pool [i].alloc_count);
        }
    } else {
        fprintf (stderr, "Slice system is not initialized.\n");
    }
}
#endif

/*
vi:ts=4:nowrap:ai:expandtab
*/
